package com.chapter4.graph.direct;

import java.util.Stack;

import com.chapter1.basic.queue.Queue;

/**
 * 
* @ClassName: DirectedBFS 
* @Description: 有向图广度优先搜索 
* @author minjun
* @date 2015年3月1日 下午6:15:32 
*
 */
public class DirectedBFS {

	private boolean[] marked;
	
	private int[] edgeTo;
	
	private int s;
	
	public DirectedBFS(Digraph d,int s){
		this.s=s;
		marked=new boolean[d.V()];
		edgeTo=new int[d.V()];
		bfs(d,s);
	}

	private void bfs(Digraph d, int v) {
		Queue<Integer> queue=new Queue<Integer>();
		marked[v]=true;
		queue.offer(v);
		while(!queue.isEmpty()){
			v=queue.poll();
			for(int w:d.adj(v)){
				if(!marked[w]){
					marked[w]=true;
					edgeTo[w]=v;
					queue.offer(w);
				}
			}
		}
	}
	
	public boolean hasPathTo(int v){
		return marked[v];
	}
	
	public Iterable<Integer> pathTo(int v){
		if(!hasPathTo(v)) throw new RuntimeException("不可达");
		Stack<Integer> path=new Stack<Integer>();
		for(int i=v;i!=s;i=edgeTo[i]){
			path.push(i);
		}
		path.push(s);
		return path;
	}
	
	public String path(int v){
		Stack<Integer> path=(Stack<Integer>) pathTo(v);
		StringBuilder sb=new StringBuilder();
		while(!path.isEmpty()){
			sb.append(path.pop()+"->");
		}
		int len=sb.length();
		if(sb.toString().endsWith("->")){
			sb.delete(len-2, len);
		}
		return sb.toString();
	}
}
